package cc.wsyw126.java.nowcoder.sword_offer;

/**
 * Created by Administrator on 2017/4/14.
 *统计一个数字在排序数组中出现的次数。
 */
public class GetNumberOfK {
    public int GetNumberOfK(int[] array, int k) {
        int left = findFirstK(array, 0, array.length - 1, k);
        int right = findLastK(array, 0, array.length - 1, k);
        if (right == -1 && left == -1) {
            return 0;
        }
        return right - left + 1;
    }

    private int findFirstK(int[] array, int left, int right, int k) {
        int mid = (right + left) / 2;
        if (left>right) return  -1;
        if (array[mid] == k && (mid == 0 || array[mid - 1] != k)) return mid;
        if (array[mid] >= k) {
            right = mid - 1;
        } else if (array[mid] < k) {
            left = mid + 1;
        }
        return findFirstK(array, left, right, k);
    }

    private int findLastK(int[] array, int left, int right, int k) {
        int mid = (right + left) / 2;
        if (left>right) return -1;
        if (array[mid] == k && (mid == right || array[mid + 1] != k)) return mid;
        if (array[mid] > k) {
            right = mid - 1;
        } else if (array[mid] <= k) {
            left = mid + 1;
        }
        return findLastK(array, left, right, k);
    }

    public static void main(String[] args) {
        GetNumberOfK getNumberOfK = new GetNumberOfK();
        int i = getNumberOfK.GetNumberOfK(new int[]{1, 2, 3, 3, 3, 6}, 0);
        System.out.println("i = " + i);
    }
}
